#include <iostream>
#include <algorithm>
#include <vector>
#include "conio.h"

using namespace std;

int number_of_unique_bst(const vector<int> a, int l, int r)
{
	if (l >= r)
		return 1;

	int n = 0;
	for (int i = l; i < r; ++i)
	{
		if (i == r - 1|| a[i] != a[i+1])
			n += number_of_unique_bst(a, l, i) * number_of_unique_bst(a, i+1, r);
	}
	
	return n;
}

void main()
{
	int n;
	cout << "Input number of numbers:" << endl;
	cin >> n;
	vector<int> numbers(n);
	cout << "Input numbers:" << endl;
	for (int i = 0; i < n; ++i)
		cin >> numbers[i];

	sort(numbers.begin(), numbers.end());
	cout << "Number of unique binary search trees: " << number_of_unique_bst(numbers, 0, numbers.size()) << endl;
	_getch();
}